history monoid について

Words near each other

Dictionary Lists

mini英和辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

history monoid ：ウィキペディア英語版

history monoid
In mathematics and computer science, a history monoid is a way of representing the histories of concurrently running computer processes as a collection of strings, each string representing the individual history of a process. The history monoid provides a set of synchronization primitives (such as locks, mutexes or thread joins) for providing rendezvous points between a set of independently executing processes or threads.
History monoids occur in the theory of concurrent computation, and provide a low-level mathematical foundation for process calculi, such as CSP the language of communicating sequential processes, or CCS, the calculus of communicating systems. History monoids were first presented by M.W. Shields.〔M.W. Shields "Concurrent Machines", ''Computer Journal'', (1985) 28 pp. 449–465.〕
History monoids are isomorphic to trace monoids (free partially commutative monoids) and to the monoid of dependency graphs. As such, they are free objects and are universal. The history monoid is a type of semi-abelian categorical product in the category of monoids.
==Product monoids and projection==
Let
:

A=(\Sigma_1,\Sigma_2,\ldots,\Sigma_n)

denote an ''n''-tuple of alphabets

\Sigma_k

. Let

P(A)

denote all possible combinations of finite-length strings from the alphabets:
:

P(A)=\Sigma_1^* \times \Sigma_2^* \times \cdots \times \Sigma_n^*

(In more formal language,

P(A)

\Sigma_k

. The superscript star is the Kleene star.) Composition in the product monoid is component-wise, so that, for
:

\bold=(u_1,u_2,\ldots,u_n) \,

and
:

\bold=(v_1,v_2,\ldots,v_n) \,

then
:

\bold=(u_1v_1,u_2v_2,\ldots,u_nv_n) \,

for all

\bold, \bold

P(A)

. Define the union alphabet to be
:

\Sigma=\Sigma_1 \cup \Sigma_2 \cup \cdots \cup \Sigma_n. \,

(The union here is the set union, not the disjoint union.) Given any string

w\in \Sigma^*

, we can pick out just the letters in some

\Sigma_k^*

using the corresponding string projection

\pi_k:\Sigma^*\to\Sigma_k^*

. A distribution

\pi:\Sigma^*\to P(A)

is the mapping that operates on

w\in \Sigma^*

with all of the

\pi_k

, separating it into components in each free monoid:
:

\pi(w)\mapsto (\pi_1(w), \pi_2(w), \ldots , \pi_n(w)). \,

翻訳と辞書 : 翻訳のためのインターネットリソース